#ifndef __GRAPH_HPP__
#define __GRAPH_HPP__

#include <vector>

struct edge
{
	int m_l, m_r;
	edge(int i_l = -1, int i_r = -1): m_l(i_l),m_r(i_r)
	{}
};

class graph
{
private:
	bool m_directed_graph;
	int m_node_count, m_edge_count;

	struct node 
	{
		int v;
		node* next;
		node(int in_v, node* t): v(in_v)
		{
			next = t;
		};
	};

	std::vector<node*> m_adj;
public:
	graph(int node_number, bool directed_graph):m_directed_graph(directed_graph), m_node_count(node_number), m_edge_count(0)
	{
		m_adj.assign(node_number, 0);
	};
	~graph()
	{
		for (std::vector<node*>::iterator it=m_adj.begin(); it != m_adj.end(); it++)
		{
			delete (*it);
		}
	};

	bool directed()
	{
		return m_directed_graph;
	};

	void remove(edge in_edge)
	{};
	
	void insert(edge in_edge)
	{
		int v = in_edge.m_l, w = in_edge.m_r;
		m_adj[v] = new node(w, m_adj[v]);
		if (!m_directed_graph)
			m_adj[w] = new node(v, m_adj[w]);
		m_edge_count++;
	};
	int V()
	{
		return m_node_count;
	}
	bool has_edge(int r, int l)
	{
		return m_adj[r]->v == l;
	};
	
	friend class adj_iterator;
	class adj_iterator
	{
		const graph& ref_graph;
		int v;
		node* t;
	public:
		adj_iterator(const graph& _graph, int v ) : ref_graph(_graph), v(v)
		{
			t = 0;
		};
		int begin()
		{
			t = ref_graph.m_adj[v];
			return t ? t->v : -1;
		};
		int next()
		{
			if ( t )
				t = t->next;
			return t ? t->v : -1;
		};
		bool end()
		{
			return t == 0;
		}
	};
};

#endif